package star.动态规划.斐波那契数列;

public class Fib {
    public static void main(String[] args) {
        System.out.println(Integer.MAX_VALUE);
        System.out.println(new Fib().fib(44));
    }
    public int fib(int n){
        if (n==0) return 0;
        if (n==1 || n==2) return 1;
        int a = 1;
        int b = 1;
        int c = a + b;
        for (int i = 3; i < n; i++) {
            a = b;
            b = c;
            c = (a + b)%1000000007;
        }
        return c;
    }
    //数组,占空间
    public int fib3(int n){
        if (n==0) return 0;
        if (n==1) return 1;
        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < arr.length; i++) {
            arr[i] = (arr[i-1] + arr[i-2])%1000000007;
        }
        return arr[n-1];
    }
    //递归,很花时间
    public int fib2(int n) {
        if (n==0) return 0;
        if (n==1) return 0;
        if (n==2) return 1;
        return (fib(n-1) + fib(n-2))>1000000007?1:fib(n-1) + fib(n-2);
    }
}
